package com.leetcode.根据数据结构分类.链表;

import com.leetcode.datastructure.ListNode;

/**
 * @author: ZhouBert
 * @date: 2021/3/18
 * @description: 92. 反转链表 II
 * https://leetcode-cn.com/problems/reverse-linked-list-ii/
 * 链表问题还是需要注意【头结点】的处理鸭！
 */
public class B_92_反转链表II {

	static B_92_反转链表II action = new B_92_反转链表II();

	public static void main(String[] args) {
		test1();
	}

	public static void test1() {
		ListNode head = new ListNode(3);
		head.next = new ListNode(5);
		int left = 1, right = 2;
		ListNode res = action.reverseBetween(head, left, right);
		ListNode.print(res);
	}


	public ListNode reverseBetween(ListNode head, int left, int right) {
		if (left == right) {
			//如果相等
			return head;
		}
		//开始反转
		int loc = 1;
		ListNode curNode = head;
		ListNode preLeftNode = null;
		while (loc < left) {
			preLeftNode = curNode;
			curNode = curNode.next;
			loc++;
		}
		//保留 反转段中的指针（末尾）
		ListNode tail = curNode;
		//此时 curNode == leftNode,准备反转
		ListNode preNode = null;
		ListNode nextNode = curNode.next;
		while (loc < right) {
			ListNode tempNode = nextNode;
			nextNode = nextNode.next;
			tempNode.next = curNode;
			curNode.next = preNode;
			preNode = curNode;
			curNode = tempNode;

			loc++;
		}
		//此时 curNode ==  rightNode
		//BUG 修复
		if (preLeftNode != null) {
			preLeftNode.next = curNode;
		}else {
			head = curNode;
		}
		//tail 不会为null ,因为为null 意味着到达末尾了，就不会存在 right
		tail.next = nextNode;
		return head;
	}

}

